1.3 Efficient quantum algorithms
既然量子信息有这么多奇特性质，我们就会期待量子理论可以更新我们对计算的认知。Peter Shor (an AT&T computer scientist and a former Caltech undergraduate)在1994年给了一个量子计算机高效地完成质因数分解的算法，堪比平地一声雷。Shor证明了，至少在原理上，量子计算机可以高效地进行质因数分解。
质因数分解是一个很难对付的(intractable)计算问题：答案一旦找到的话很容易验证，只要相乘就可以了；但难点就在于答案很难找到。如果和是很大的质数，那么他们的乘积很容易计算，所需要的基本的位操作(bit operations)数大约是。但是，给定，要找到和就很难了。
用经典计算机进行质因数分解，大家公认需要的超越多项式(superpolynomial)时间（虽然还没被严格证明），即当$n$增长时，最差情况需要的时间比的任何次幂都大。已知的最好算法(number field sieve算法)需要耗时约 目前最大的运算量是几百个工作站算一个月，将130位数分解成65位数。由此推算，分解400位数需要$10^{10}$年，相当于宇宙年龄！因此，即便科技大幅进步，质因数分解400位数仍旧是个遥不可及的梦想。
质因数分解问题，从复杂性理论（complexity theory ）角度看，是一类有趣的难解问题，即无法在（输入大小的）多项式时间内解决的问题，在上例中输入大小即为。从实践角度看，它也是很有实际应用价值的一类问题，因为质因数分解的难度就是现代公钥加密技术的基础，比如RSA加密技术。
然而Shor发现，量子计算机竟然可以在多项式时间内完成质因数分解计算！因此，假设我们已经有了量子计算机，它能在一个月内质因数分解一个130位的数，那么它能在3年内就质因数分解一个400位的数。问题越难（位数越多），量子计算机的优势就越明显。在量子计算机面前，现有的RSA技术将无法保密。
Shor的结果激发了我（本书中“我”皆代表作者Preskill，译者注）对量子信息的兴趣，如果不是Shor，我觉得我也不会教这门课。思考Shor的结果对于复杂性理论、量子理论和技术应用是很有意思的一件事。